package sysu.el.graph.undi.algor;

import sysu.el.array.BoolArray;
import sysu.el.array.algors.Sig;
import sysu.el.array.ints.ArrQueueInt;
import sysu.el.graph.tree.FatherTreeTopo;
import sysu.el.graph.tree.FatherTreeTopoInt;
import sysu.el.graph.undi.UndiGT;
import sysu.el.graph.undi.UndiGTAdjList;

public class MSTCreator {
	// Reference
	public UndiGT graph;
	
	// Created
	public UndiGTAdjList tree;
	
	// Algorithm Data
	public BoolArray isVisited;
	public ArrQueueInt queue;
	
	public MSTCreator(UndiGT g){
		graph = g;
		isVisited = new BoolArray(g.getNodeNum());
	}
	
	public FatherTreeTopo getTree(int root){
		if (tree == null)
			return createOneTree(root);
		
		FatherTreeTopo ft = new FatherTreeTopo(graph.getNodeNum());
		ft.setRoot(root);
		
		// Reuse
		isVisited.reset();
		queue.reset();
		
		// 
		isVisited.setVisited(root);
		queue.add(root);
		while (queue.isEmpty()){
			int h = queue.getHead();
			int[] list = tree.getList(h);
			for (int i = list.length-1; i>=0; i--){
				queue.add(list[i]);
				ft.addEdge(h, list[i]);
			}
		}
		
		return ft;
	}

	/**
	 * Relevant of the isVisited
	 * @param root
	 * @return The tree have a value... 
	 * primitive type of ft in the return value is FatherTreeTopoInt 
	 * you should cast FatherTreeTopo to FatherTreeTopoInt then you got a value
	 */
	public FatherTreeTopoInt createOneTree(int root){
		FatherTreeTopoInt ft = new FatherTreeTopoInt(graph.getNodeNum(), Integer.MAX_VALUE);
		tree = new UndiGTAdjList(graph.getNodeNum());
		isVisited.reset();
		ft.root = root;
		ft.fa[root] = root;
		ft.val[root] = 0;
		int cur = root;
//		int newCur = root;
//		for (int i=0; i<graph.getNodeNum()-1; i++){
//		for (Bomb.c4.start(graph.getNodeNum()-1); Bomb.c4.survive(); Bomb.c4.tick()){
//		for (int i=graph.getNodeNum()-1; i>0; i--){
		
		int counter = graph.getNodeNum() - 1;
		do{
			// Update
			isVisited.setVisited(cur);
			for (int j=graph.getDegree(cur)-1; j>=0; j--){
				int id = graph.getList(cur)[j];
				if ((isVisited.isUnvisited(id))	&& (ft.val[id] > graph.getW(cur, id))
						/*||(ft.val[id]==0)*/	){
					ft.val[id] = graph.getW(cur, id);
					ft.fa[id] = cur;
				}
			}
			System.out.println(Sig.mkString(ft.fa, ", "));
			int minId = -1;
			int minVal = Integer.MAX_VALUE;
			for (int j=graph.getNodeNum()-1; j>=0; j--){
				if ((isVisited.isUnvisited(j) && (ft.val[j] < minVal))){
					minId = j;
					minVal = ft.val[j];
				}
			}
			
//			tree.addEdge(ft.fa[minId], minId);
			System.out.println(ft.fa[minId] + "\t" + minId);
			tree.addEdge(ft.fa[minId], minId);
			ft.sum += minVal;
			cur = minId;
		}while(--counter > 0);

		return ft;
	}
	
	
	
	
	
}
